package data_structures_and_algorithms.tree.learn;

import common.TreeNode;

/**
 * @ClassName Code_zuo_god_maxInstance_In_tree
 * @Description: TODO
 * @Author: yongliang.ma
 * @Create_time:2022/10/30 18:11
 */
public class Code_zuo_god_maxInstance_In_tree {
    public class Info{
        int maxInstance;
        int height;
        public Info(int maxInstance, int height){
            this.maxInstance = maxInstance;
            this.height = height;
        }
    }

    // 注意看这里分析问题的思路：二叉树的DP思想
    public int getMaxInstance(TreeNode root){
        return dfs(root).maxInstance;
    }
    public Info dfs(TreeNode node){
        if (node == null)
            return new Info(0, 0);

        // 收集左右孩子的信息
        Info LInfo = dfs(node.left);
        Info RInfo = dfs(node.right);
        int maxInstance = Math.max(Math.max(LInfo.maxInstance, RInfo.maxInstance), LInfo.height + RInfo.height + 1);
        int maxHeight = Math.max(LInfo.height, RInfo.height) + 1;// 高度 需要算上本节点自己的高度

        return new Info(maxInstance, maxHeight);
    }

}
